Write a recursive function for generating all permutations of an input string. Return them as a set.
Don't worry about time or space complexity—if we wanted efficiency we'd write an iterative version.
To start, assume every character in the input string is unique.
Your function can have loops—it just needs to also be recursive.
If we're making all permutations for "cat," we take all permutations for "ca" and then put "t" in each possible position in each of those permutations. We use this approach recursively:
def get_permutations(string):
# Base case
if len(string) <= 1:
return set([string])
all_chars_except_last = string[:-1]
last_char = string[-1]
# Recursive call: get all possible permutations for all chars except last
permutations_of_all_chars_except_last = get_permutations(all_chars_except_last)
# Put the last char in all possible positions for each of
# the above permutations
permutations = set()
for permutation_of_all_chars_except_last in permutations_of_all_chars_except_last:
for position in range(len(all_chars_except_last) + 1):
permutation = (
permutation_of_all_chars_except_last[:position]
+ last_char
+ permutation_of_all_chars_except_last[position:]
)
permutations.add(permutation)
return permutations
How does the problem change if the string can have duplicate characters?
What if we wanted to bring down the time and/or space costs?
This is one where playing with a sample input is huge. Sometimes it helps to think of algorithm design as a two-part process: first figure out how you would solve the problem "by hand," as though the input was a stack of paper on a desk in front of you. Then translate that process into code.
Do you have an answer?
Wanna review this one again later? Or do you feel like you got it all?
Mark as done Pin for review laterReset editor
Powered by qualified.io